/**
 * @param {number[][]} edges
 * @return {number[]}
 */
var findRedundantConnection = function(edges) {
  let graph = new Map();
  // 添加边
  function addEdge(edge) {
    // 这个点是否有加入过map
    // 1.加入过map，则拿到这个数组，并且push
    // 2.没加入过map，直接创建一个数组加入过去
    if(graph.has(edge[0]) && graph.get(edge[0]).indexOf(edge[1]) == -1) {
      graph.get(edge[0]).push(edge[1]);
    } else {
      graph.set(edge[0], [edge[1]]);
    }
    if(graph.has(edge[1]) && graph.get(edge[1]).indexOf(edge[0]) == -1) {
      graph.get(edge[1]).push(edge[0]);
    } else {
      graph.set(edge[1], [edge[0]]);
    }
  }
  let visited = [];
  // 深搜
  /**
   *
   * @param {原节点} source
   * @param {目的节点} target
   * @returns
   */
  function dfs(source, target) {
    if(!graph.has(source)) {
      let temp = source;
      source = target;
      target = temp;
    }
    // 该节点已被访问过
    if(graph.get(source).indexOf(target) !== -1) {
      return true;
    } else {
      for(let i = 0; i < graph.get(source).length; i++) {
        visited[source - 1] = true;
        // console.log("source", source, "target", target, "graph.get(source)", graph.get(source), visited);
        if(visited[graph.get(source)[i] - 1])
          continue;
        // 没被访问过,并且dfs中返回为true的话，就是说明source可以到达target
        if(dfs(graph.get(source)[i], target)) {
          return true;
        }
      }

    }
    return false;
  }

  // 开始遍历
  for(let edge of edges) {
    // 如果这条边中的两个节点都没有在图中出现过，则需要添加这条边
    if(!graph.has(edge[0]) && !graph.has(edge[1])) {
      addEdge(edge);
    } else {
      // 两个节点在图中，深度优先遍历图，是否能找到从u到v的路劲，
      // 如果能找到，该边就是冗余边，否则，该边就不是冗余边
      visited = new Array(edges.length).fill(false);
      // console.log(`${edge[0]}是否能够到达${edge[1]}-${dfs(edge[0], edge[1])}`);
      visited = new Array(edges.length).fill(false);
      if (dfs(edge[0], edge[1])) {
        return edge;
      } else {
        addEdge(edge)
      }
    }
  }
};
let edges = [[1,2], [1,3], [2,3]];
console.log(findRedundantConnection(edges));
edges = [[1,2], [2,3], [3,4], [1,4], [1,5]];
console.log(findRedundantConnection(edges));
edges = [[1,4],[3,4],[1,3],[1,2],[4,5]];
console.log(findRedundantConnection(edges));

